package test230609;

import java.util.HashMap;
import java.util.Map;

/**
 * @author 兴趣使然黄小黄
 * @version 1.0
 * @date 2023/6/9 17:47
 * 409. 最长回文串
 * https://leetcode.cn/problems/longest-palindrome/
 */
public class Solution01 {

    public int longestPalindrome(String s) {
        // 构造哈希表用于统计每个字符出现的次数
        HashMap<Character, Integer> counter = new HashMap<>();
        for (char c : s.toCharArray()) {
            counter.put(c, counter.getOrDefault(c, 0) + 1);
        }
        // 如果字符出现次数为偶数, 则能加入到结果的长度中
        // 如果字符出现的次数为奇数, 则可以将其放在中间, 且整个字符串只能放一个, 计为 odd
        // 如果是奇数, 则 odd 置为 1, 且 向下取偶数
        int res = 0;
        int odd = 0;
        for (Map.Entry<Character, Integer> entry : counter.entrySet()) {
            Integer count = entry.getValue();
            int temp = count % 2;
            res += count - temp;
            if (temp == 1) {
                odd = 1;
            }
        }
        return res + odd;
    }
}
